import java.util.Arrays;

public class Leetcode4_寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        Solution14 solution14 = new Solution14();
        System.out.println(solution14.findMedianSortedArrays(new int[]{1, 3}, new int[]{2, 4}));
    }
}


class Solution14 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // p1为num1数组指针，p2为nums2数组指针，p为合并数组的指针
        int p1 = 0, p2 = 0, p = 0;
        int[] mergeArray = new int[nums1.length + nums2.length];

        // 合并数组，保持递增
        while (p < mergeArray.length) {
            // System.out.println(String.format("%d %d %d %s", p1, p2, p, Arrays.toString(mergeArray)));
            // 当数组1取尽，数组2未取尽时
            if (p1 >= nums1.length && p2 < nums2.length) {
                mergeArray[p++] = nums2[p2++];
                continue;
            }
            // 当数组2取尽，数组1未取尽时
            if (p2 >= nums2.length && p1 < nums1.length) {
                mergeArray[p++] = nums1[p1++];
                continue;
            }

            // 当数组1和数组2均未取尽时，将小的值插入mergeArray
            if (nums1[p1] < nums2[p2]) {
                mergeArray[p++] = nums1[p1++];
            } else {
                mergeArray[p++] = nums2[p2++];
            }
        }
        //System.out.println(Arrays.toString(mergeArray));
        // 求中位数
        int d = mergeArray.length / 2;
        if (mergeArray.length % 2 == 1) {
            return mergeArray[d];
        } else {
            return (double) (mergeArray[d] + mergeArray[d-1]) / 2;
        }
    }
}